Định nghĩa Đường_đi_Hamilton

Cho đồ thị G = (V,E), có n đỉnh

Đường đi x0,x1,...,xn-1,xn là đường đi Hamilton nếuV = {x0,x1,...,xn-1,xn}xi!=xj, 0 ≤ i < j ≤ n

Chu trình x0,x1,...,xn,x0 là chu trình Hamilton nếu x0,x1,...,xnlà đường đi Hamilton

  • Dây chuyền Hamilton là dây chuyền đi qua các đỉnh của đồ thị và đi qua mỗi đỉnh đúng 1 lần.
  • Chu trình Hamilton là dây chuyền Hamilton xuất phát từ một đỉnh, đi qua tất cả các đỉnh khác của đồ thị, mỗi đỉnh đúng một lần và quay trở về nơi xuất phát.
  • Đồ thị Hamilton là đồ thị có chứa ít nhất một chu trình Hamilton.